package sort;

import com.alibaba.fastjson.JSON;

/**
 * \* User: MeiZhongHao
 * \* Date: 2019-04-09
 * \* Time: 17:59
 * \* Description:
 * \
 */
public class HeapSort {


//    3, 2, 5, 12, 153, 53, 21, 22, 97
//    i = 4 :
//    i = 3 : 3, 2, 5, 22, 153, 53, 21, 12, 97
//    i = 7 :
//    i = 2 : 3, 2, 153, 22, 5, 53, 21, 12, 97
//    i = 4 : 3, 2, 153, 22, 97, 53, 21, 12, 5
//    i = 8 :
//    i = 1 : 3, 153, 2, 22, 97, 53, 21, 12, 5
//    i = 2 : 3, 153, 97, 22, 2, 53, 21, 12, 5
//    i = 4 : 3, 153, 97, 22, 5, 53, 21, 12, 2
//    i = 8 :
//    i = 0 : 153, 3, 97, 22, 5, 53, 21, 12, 2
//    i = 1 : 153, 97, 3, 22, 5, 53, 21, 12, 2
//    i = 2 : 153, 97, 53, 22, 5, 3, 21, 12, 2
//    i = 5 :
//
//// 构建好大顶堆后
//            2, 97, 53, 22, 5, 3, 21, 12, 153 [len = 8]
//    i = 0 : 97, 2, 53, 22, 5, 3, 21, 12, 153
//    i = 1 : 97, 53, 2, 22, 5, 3, 21, 12, 153
//    i = 2 : 97, 53, 5, 22, 2, 3, 21, 12, 153
//    i = 4 :
//
//            12, 53, 5, 22, 2, 3, 21, 97, 153 [len = 7]
//    i = 0 : 53, 12, 5, 22, 2, 3, 21, 97, 153
//    i = 1 : 53, 22, 5, 12, 2, 3, 21, 97, 153
//    i = 3 : 53, 22, 5, 21, 2, 3, 12, 97, 153
//
//
//            12, 22, 5, 21, 2, 3, 53, 97, 153 [len = 6]
//    i = 0 : 22, 12, 5, 21, 2, 3, 53, 97, 153
//    i = 1 : 22, 21, 5, 12, 2, 3, 53, 97, 153
//    i = 3 :
//
//            3, 21, 5, 12, 2, 22, 53, 97, 153 [len = 5]
//    i = 0 : 21, 3, 5, 12, 2, 22, 53, 97, 153
//    i = 1 : 21, 12, 5, 3, 2, 22, 53, 97, 153
//    i = 3 :
//
//            2, 12, 5, 3, 21, 22, 53, 97, 153 [len = 4]
//    i = 0 : 12, 2, 5, 3, 21, 22, 53, 97, 153
//    i = 1 : 12, 5, 2, 3, 21, 22, 53, 97, 153
//    i = 2 :
//
//            3, 5, 2, 12, 21, 22, 53, 97, 153 [len = 3]
//    i = 0 : 5, 3, 2, 12, 21, 22, 53, 97, 153
//    i = 1 :
//
//            2, 3, 5, 12, 21, 22, 53, 97, 153 [len = 2]
//    i = 0 : 3, 2, 5, 12, 21, 22, 53, 97, 153
//    i = 1
//
//            2, 3, 5, 12, 21, 22, 53, 97, 153 [len = 1]
//    i = 0 :
//
//            2, 3, 5, 12, 21, 22, 53, 97, 153
    static int len;

    public static int[] heapSort(int[] array) {
        len = array.length;
        if (len < 1) {
            return array;
        }
        // 构建一个最大堆
        buildMaxHeap(array);
        // 循环将堆首位（最大值）与末位交换，然后重新调整最大堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0);
        }
        return array;
    }

    /***
     * 堆调整
     * @param array
     * @param i
     */
    private static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        // 如果左子树且左子树大于父节点，则将最大指针指向左子树
        if (i * 2 < len && array[i * 2] > array[maxIndex]) {
            maxIndex = i * 2;
        }
        // 如果右子树且右子树大于父节点，则将最大指针指向右子树
        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) {
            maxIndex = i * 2 + 1;
        }
        // 如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }

    private static void swap(int[] array, int i, int i1) {
        int temp = array[i];
        array[i] = array[i1];
        array[i1] = temp;
    }

    /***
     * 建立大顶堆，从最后一个非叶子节点开始向上构建最大堆
     * @param array
     */
    private static void buildMaxHeap(int[] array) {
        for (int i = (len - 1) / 2; i >= 0; i--) {
            adjustHeap(array, i);
        }
    }

    public static void main(String[] args) {
        int[] i = new int[]{3, 2, 5, 12, 153, 53, 21, 22, 97};
        System.out.println(JSON.toJSONString(heapSort(i)));
    }

}